An autorouter is a collection of algorithms that attempt to find a set of wire segments (line segments on a routing layer, also referred to as “nets”) and a set of vias (connections between routing layers) that connect terminals (component pins) while at the same time satisfying a set of known design constraints, such as design rules. To do so, they make an enormous number of tiny decisions. Typically these decisions made by the algorithms in a typical autorouter are based on numerically computed “costs”. That is when faced with alternate choices, the algorithms select the lower cost alternative.
Early in the history of the electronic design automation (EDA) industry, circuit designs had only physical constraints to meet. For example, consider the design rule of maintaining a minimum clearance between two routing segments for different nets. In this environment, the “cost” was the length of the routing segments. A shorter length meant less space used resulting in lower costs and hence, a greater likelihood of finding a complete solution.
As clock speeds increased, timing constraints were introduced such as “maximum delay” constraints. That is, not only did the autorouter need to minimize the total length of a wire segment but it had to do so in a way that didn't exceed the maximum delay rules for these nets. The added complexity of having to meet timing constraints was solved by algorithms that either first routed the delay-constrained nets or changed the cost function so that the length for these delay-constrained nets had a higher cost so that they would have a greater priority in routing over other nets with lower costs.
As clock frequencies continued to increase further still, additional design constraints were added to routing a circuit layout. Algorithms were provided in autorouters to try to further adapt by either routing the additional constrained nets first or by further tuning cost functions.
However, using these two approaches to meet additional design constraints for routing a circuit design are reaching their limits and can no longer be extended. For example, in today's high-end printed circuit board designs it may be impossible to route the constrained nets first because almost every net now has a design constraint to meet. In fact, many nets have multiple design constraints to meet. The multiple design constraints when attempting to route a net may interact and make it difficult, if not impossible, to further tune the cost functions as the different constraints for a net cannot be expressed as a single numeric value. Furthermore with numerous constraints for routing a design, it is common for the constraints to conflict.
Referring now to background FIG. 1, an exemplary portion of a circuit layout 100 is illustrated to explain how multiple design constraints may conflict. The circuit layout 100 has a pair of top pins 109, 110 and a bottom pin 111. Nets or wire segments 104-108 route between the pair of top pins 109, 110 and the bottom pin 111.
A first exemplary design constrain 121, a maximum crosstalk constraint, requires that the two nets 105,106 be spaced further apart by a spacing 140 than minimum spacing so that signals on each are not distorted. For comparison, minimum spacing may be illustrated by the spacing 145 between nets 104,105.
A second exemplary design constraint 122, a minimum delay constraint, requires that the net 107 use a serpentine path so that the signals thereon do not arrive too early. This constraint may require significant area to route the net 107 in comparison with the net 108 as illustrated.
A third exemplary design constraint 123, a pin entry constraint, requires that a track segment 133 can only enter pin 111 from the narrow end 141 in contrast to the long end 142 as shown in order to reduce manufacturing yield problems.
These constraints are further constrained by the positioning of the pair of top pins 109, 110 and the bottom pin 111 and the limited amount of space between them.
It is difficult, if not impossible, to concurrently satisfy all of these constraints when routing. Clearly there is a pad exit problem at the bottom pin 111, particularly if pad 111 is fixed in position and the spacing 150 between net 108 and track segment 133 is already at a minimum spacing.
Thus, there is a need for a new approach to represent and process multiple design constraints in an autorouter for routing nets of electronic circuit designs.